public class MaxSubArray {
    // 最大子数组和
    // https://leetcode.cn/problems/maximum-subarray/?envType=study-plan-v2&envId=top-100-liked
    public int maxSubArray(int[] nums) {
        // dp[i]表示以第i个位置为结尾的子数组的最大子数组和
        // 那么以第i个位置为结尾的话，就有两种情况：
        // 1. 接在前i-1个元素形成的最大子数组的后面形成新的最大子数组
        // 2. 当前元素单独为一个最大子数组
        // dp[i]的最大值就是上面两种情况的最大值
        int[] dp = new int[nums.length+1];
        dp[0] = -0x3f3f3f3f;
        int ret = -0x3f3f3f3f;
        for (int i = 1; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i-1],nums[i-1]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    /**
     * 空间优化，因为根据状态转移方程，dp[i]只和dp[i-1]有关，所以可以空间优化
     * @param nums
     * @return
     */
    public int maxSubArray1(int[] nums) {
        // dp[i]表示以第i个位置为结尾的子数组的最大子数组和
        // 那么以第i个位置为结尾的话，就有两种情况：
        // 1. 接在前i-1个元素形成的最大子数组的后面形成新的最大子数组
        // 2. 当前元素单独为一个最大子数组
        // dp[i]的最大值就是上面两种情况的最大值
        int prev = -0x3f3f3f3f;
        int ret = -0x3f3f3f3f;
        for (int i = 1; i <= nums.length; i++) {
            prev = Math.max(prev+nums[i-1],nums[i-1]);
            ret = Math.max(ret, prev);
        }
        return ret;
    }
}
